package merkleTree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class Tree 
{
	public Tree parent, lchild, rchild;
	
	/**
	 * hash of each node,
	 * if leaf node then hash = hash(data) , else hash = hash { hash(left) || hash(right) }
	 */
	private int hash;
	private int data;
	
	/**
	 * this map holds all (data,node) pairs,
	 * it helps in searching requested element and then finding proof for it
	 */
	private static Map<Integer, Tree> map;
	private static StringBuffer sball = new StringBuffer();
	
	/**
	 * Constructor
	 * @param lc left child of the node to create
	 * @param rc right child of the node to create
	 * @param data the data content of the node to create
	 */
	public Tree(Tree lc, Tree rc, int data) 
	{
		lchild = lc;
		rchild = rc;
		parent = null;
		this.data = data;
		
		if(lc == null)
			hash = hash(data);
		else
			hash = computeHash(lchild.getHash(), rchild.getHash());
	}
	
	/**
	 * @param t the node whom to set as parent
	 */
	public void setParent(Tree t) 
	{
		parent = t;
	}
	
	/**
	 * @return the parent of the node
	 */
	public Tree getParent() 
	{
		return parent;
	}
	
	/**
	 * @return the hash of the node
	 */
	public int getHash() 
	{
		return hash;
	}
	
	/**
	 * @param lhash the hash of left child
	 * @param rhash the hash of right child
	 * @return the hash computed by concatenating left child and right child respectively
	 */
	public static int computeHash(int lhash, int rhash) 
	{
		//String cat = "" + lhash + rhash;
		//int value = Integer.parseInt(cat);
		long value = lhash+rhash;
		return hash(value);
	}
	
	/**
	 * Checks if a given node is a leaf node or not
	 * @param node Node to check
	 * @return true if given node is a leaf node , false otherwise
	 */
	private boolean isLeaf(Tree node)
	{
		if((node.lchild == null) && (node.rchild == null))
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	
	/** Updates the hashes bubbling upwards till root
	 * @param element The node from which to start recomputing hashes
	 */
	private void updateHashes(int element) 
	{
		Tree x = map.get(element);
		Tree parent_x = x.getParent();
		while(parent_x!= null) 
		{
			parent_x.hash = computeHash(parent_x.lchild.getHash(), parent_x.rchild.getHash());
			x = parent_x;
			parent_x = x.getParent();
		}
	}
	
	/** Updates the hashes bubbling upwards till root
	 * @param elementNode The node from which to start recomputing hashes
	 */
	private void updateHashes(Tree elementTree) 
	{
		Tree x = elementTree;
		Tree parent_x = x.getParent();
		while(parent_x!= null) 
		{
			parent_x.hash = computeHash(parent_x.lchild.getHash(), parent_x.rchild.getHash());
			x = parent_x;
			parent_x = x.getParent();
		}
	}
	
	/** Tells whether a given number is a power of two
	 * @param number to check
	 * @return True if the number is a power of 2, false otherwise
	 */
	private boolean isPowerOf2(int number) 
	{
		if(number == 0) return false;
		
		if( (number & (number - 1)) == 0 )
		{
			return true;
		}
		return false;
	}
	
	private String printtabs(int n)
	{
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<n;i++)
		{
			sb.append("\t");
		}
		return sb.toString();
	}
	
	/** Calculates the height of a given tree
	 * @param node The tree whose height is to be computed
	 * @return the height of the tree is returned (if only root then height = 1)
	 */
	private int height(Tree node)
	{
		   if (node==null)
		       return 0;
		   else
		   {
		     /* compute the height of each subtree */
		     int lheight = height(node.lchild);
		     int rheight = height(node.rchild);
		 
		     /* use the larger one */
		     if (lheight > rheight)
		         return(lheight+1);
		     else return(rheight+1);
		   }
	}
	
	/**
	 * Prints a given level of the tree
	 * @param root The tree to print
	 * @param level The level starting from 1 (root has level = 1)
	 * @param height The max level of the tree
	 */
	private void printGivenLevel(Tree root, int level, int height)
	{
	  if(root == null)
	    return;
	  if(level == 1)
		  sball.append("a(" + root.data + "," + root.hash + ")b");
	  else if (level > 1)
	  {
	    printGivenLevel(root.lchild, level-1, height);
	    printGivenLevel(root.rchild, level-1, height);
	  }
	}
	
	/*
	 * Displays the tree elements top-down, each level in one line
	 */
	public void printLevelOrder()
	{
	  System.out.println();
	  int h = height(this);
	  int i;
	  for(i=1; i<=h; i++)
	  {
		  printGivenLevel(this, i, h);
		  String sbs = sball.toString();
		  int x = (int)Math.pow(2,h-i);
		  int y = x - 1;
		  sbs = sbs.replaceAll("a",printtabs(x));
		  sbs = sbs.replaceAll("b",printtabs(y));
		  System.out.println(sbs);
		  sball.delete(0,sball.length());
		  System.out.println();
	  }
	}
	
	/**
	 * Display the in-order traversal of the tree
	 */
	public void printTreeInorder() 
	{
		if(lchild != null)
			lchild.printTreeInorder();
		System.out.println(data + "\t" + hash);
		if(rchild != null)
			rchild.printTreeInorder();
	}
	
	/*
	 * TODO To be implemented: hash function, e.g. SHA-3
	 */
	/**
	 * @param data the data content of the node
	 * @return the hash of the leaf node using its data
	 */
	public static int hash(long data) 
	{
		return (int) (data);
	}
	
	/**
	 * This function creates a tree from an array of data elements
	 * @param elements the array of data elements, which will form the leaves of the tree
	 * @return The root of the constructed Binary Tree
	 */
	public static Tree createTree(int[] elements) 
	{
		map = new HashMap<Integer, Tree>(elements.length);
		for(int i = 0; i < elements.length; i++) 
		{
			map.put(elements[i], new Tree(null, null, elements[i]));
		}
		int i;
		ArrayList<Tree> gen = new ArrayList<Tree>(map.values());
		while(gen.size()>1) 
		{
			ArrayList<Tree> nextGen = new ArrayList<Tree>();
			for(i = 0; i < gen.size()-1; i+=2) 
			{
				Tree lc = gen.get(i);
				Tree rc = gen.get(i+1);
				Tree t = new Tree(lc, rc, 0);
				lc.setParent(t);
				rc.setParent(t);
				nextGen.add(t);
			}
			if(i == gen.size()-1) 
			{
				nextGen.add(gen.get(i));
			}
			gen = nextGen;
		}
		return gen.get(0);
	}
	
	/**
	 * This function returns a proof for a requested data element
	 * @param element requested by end user
	 * @return the proof i.e, a list of hashes is returned if element exists, 
	 * returns null if element does not exist in the tree
	 */
	public static ArrayList<Integer> proofMembership(int element) 
	{
		if(!map.containsKey(element))
		{
			System.out.println("The element " + element + "does not exist");
			return null;
		}
		Tree t = map.get(element);
		ArrayList<Integer> hashes = new ArrayList<Integer>();
		hashes.add(t.getHash());
		Tree p = t.getParent();
		while(p!= null) 
		{
			if(p.lchild==t)
				hashes.add(p.rchild.getHash());
			else
				hashes.add(p.lchild.getHash());
			hashes.add(p.getHash());
			t = p;
			p = p.getParent();
		}
		return hashes;
	}
	
	/**
	 * This function inserts a given element and returns the root of the Tree
	 * @param root The tree on which element needs to be inserted
	 * @param element the data element to be inserted to the tree
	 * @return the root of the Tree with element inserted
	 */
	public Tree insert(Tree root , int element)
	{
		System.out.println("\nInserting "+ element + "\n");
		if(map.containsKey(element))
		{
			System.out.println("Element already exists");
			return root;
		}
		
		// if tree has 2^h leaf nodes , then insert another Tree one level above
		int tree_size_before = map.size();
		if(isPowerOf2(tree_size_before))
		{
			Tree rightchild = new Tree(null , null , element);
			map.put(element, rightchild);
			Tree leftchild = root;
			Tree newroot = new Tree(leftchild , rightchild , 0);
			leftchild.setParent(newroot);
			rightchild.setParent(newroot);
			return newroot;
		}
		else
		{
			// Now split into odd and even case
			if((tree_size_before % 2) == 1)
			{
				Tree required_node = root;
				while( !(isLeaf(required_node)) )
						{
							required_node = required_node.rchild;
						}
				required_node = required_node.getParent();
				// now required_node is the node on which we will create a new right child
				Tree leftchild = required_node.rchild;
				Tree rightchild = new Tree(null , null , element);
				map.put(element, rightchild);
				Tree newRightChild = new Tree(leftchild , rightchild , 0);
				leftchild.setParent(newRightChild);
				rightchild.setParent(newRightChild);
				required_node.rchild = newRightChild;
				newRightChild.setParent(required_node);				
			}
			else
			{
				// utilize the fact that we know number of leaves in the tree
				// and determine the position of new node to be inserted
				int leftsubtreesize, currenttreesize = tree_size_before;
				Tree my_required_node = root;
				do
				{
					my_required_node = my_required_node.rchild;
					leftsubtreesize = (int) Math.pow(2, (int) Math.floor(Math.log(currenttreesize)/Math.log(2)));
					currenttreesize = currenttreesize - leftsubtreesize;
				}while(!isPowerOf2(currenttreesize));
				// now my_required_node is the node to which a right sibling will be created
				Tree mainparent = my_required_node.getParent();
				Tree rightchild = new Tree(null , null , element);
				map.put(element, rightchild);
				Tree leftchild = my_required_node;
				Tree newTree = new Tree(leftchild , rightchild , 0);
				leftchild.setParent(newTree);
				rightchild.setParent(newTree);
				newTree.setParent(mainparent);
				mainparent.rchild = newTree;
			}
			updateHashes(element);
			return root;
		}
	}
	/** This function will delete the given element from the tree and return the updated root
	 * @param element : The element to be deleted
	 * @return Return the new root after deleting
	 * @throws Exception 
	 */
	public Tree delete(Tree root , int element) throws Exception
	{
		System.out.println("\nDeleting "+ element + "\n");
		if(!map.containsKey(element))
		{
			throw new Exception("Element " + element + " not found");
		}
		Tree elementTree = map.get(element);
		int size_of_tree = map.size();
		
		// checking if number of leaves of tree = 2^k + 1
		if(isPowerOf2(size_of_tree - 1))
		{
			Tree nodeToDelete = root.rchild;
			if(!(nodeToDelete==elementTree))
			{
				int temp = nodeToDelete.data;
				nodeToDelete.data = elementTree.data;
				elementTree.data = temp;
				elementTree.hash = Tree.hash(elementTree.data);
				map.remove(element);
				map.remove(elementTree.data);
				map.put(elementTree.data, elementTree);
				updateHashes(elementTree.data);
			}
			else
			{
				map.remove(element);
			}
			Tree newRoot = root.lchild;
			newRoot.parent = null;
			return newRoot;
		}
		Tree currentNode = root;
		while(currentNode.rchild != null)
		{
			currentNode = currentNode.rchild;
		}
		Tree nodeToDelete = currentNode;
		if(!(nodeToDelete==elementTree))
		{
			int temp = nodeToDelete.data;
			nodeToDelete.data = elementTree.data;
			elementTree.data = temp;
			elementTree.hash = Tree.hash(elementTree.data);
			map.remove(element);
			map.remove(elementTree.data);
			map.put(elementTree.data, elementTree);
			updateHashes(elementTree.data);
		}
		else
		{
			map.remove(element);
		}
		Tree nodeToReplace = nodeToDelete.parent;
		// case when tree has only 2 nodes and we want to delete one node
		if(nodeToReplace == root)
		{
			Tree newRoot = root.lchild;
			newRoot.parent = null;
			return newRoot;
		}
		Tree nodeToReplaceWith = nodeToReplace.lchild;
		Tree parentOfReplacedNode = nodeToReplace.parent;
		parentOfReplacedNode.rchild = nodeToReplaceWith;
		nodeToReplaceWith.parent = parentOfReplacedNode;
		updateHashes(nodeToReplace);
		return root;
	}
	
	/** This function updates an old value in the tree with a new value
	 * @param root The tree to update
	 * @param oldValue The value which will be replaced
	 * @param newValue The value to replace with
	 * @return The new Tree returned after updating
	 * @throws Exception 
	 */
	public Tree update(Tree root, int oldValue, int newValue) throws Exception
	{
		System.out.println("\nUpdating "+ oldValue + " to " + newValue + "\n");
		if(!map.containsKey(oldValue))
		{
			throw new Exception("Element " + oldValue + " not found");
		}
		if(map.containsKey(newValue))
		{
			throw new Exception("Element " + newValue + " already present");
		}
		Tree elementTree = map.get(oldValue);
		elementTree.data = newValue;
		elementTree.hash = Tree.hash(elementTree.data);
		map.remove(oldValue);
		map.put(newValue,elementTree);
		updateHashes(newValue);
		return root;
	}
	
}